// 在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。(92)
// 1) 第一个皇后先放第一行第一列
// 2) 第二个皇后放在第二行第一列、然后判断是否OK[即判断是冲突]， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
// 3) 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
// 4) 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
// 5) 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

// 理论上应该创建一个二维数组来表示棋盘 但实际上可以用一个一维数组来解决问题
// arr[8]=[0,4,7,5,2,6,1,3] 对应的下标表示第几行 arr[i]=val val表示第i+1个皇后 放在i+1行的第val+1列

class Queue8 {
    #max = 8 // 表示右多少个皇后
    #array = Array(this.#max) // 保存皇后位置的结果
    #count = 0

    /**
     * 放置第n个皇后
     * @param n
     */
    check (n) {
        if (n === this.#max) {
            this.print()
            return
        }

        // 依次放入皇后，判断是否右冲突
        for (let i = 0; i < this.#max; i++) {
            // 把皇后n 放到该行第一列
            this.#array[n] = i
            if (this.judge(n)) { // 不冲突
                this.check(n + 1)
            }
            // 如果冲突 就回到this.#array[n] = i 即将第n个皇后放在本行的后一个位置
        }
    }

    /**
     * 检查该皇后与前面已摆放的皇后是否冲突
     * @param n
     */
    judge (n) {
        for (let i = 0; i < n; i++) {
            // this.#array[i]===this.#array[n] 是否在同一列
            // Math.abs(n - i) === Math.abs(this.#array[n] - this.#array[i]) 是否在同一斜线上
            if (this.#array[i] === this.#array[n] || Math.abs(n - i) === Math.abs(this.#array[n] - this.#array[i])) {
                return false
            }
        }
        return true
    }

    print () {
        this.#count++
        console.log(this.#array.toString())
    }

    count () {
        return this.#count
    }
}

function test () {
    let q8 = new Queue8()
    q8.check(0)
    console.log(q8.count())
}

test()
